package com.gxc.hash;

import java.util.HashMap;

/**
 * 设计一种结构，在该结构中有如下三个功能:
 * insert(key):将某个key加入到该结构，做到不重复加入
 * delete(key):将原本在结构中的某个key移除
 * getRandom():等概率随机返回结构中的任何一个key。
 * [要求]
 * Insert、delete和getRandom方法的时间复杂度都是0(1)
 */
public class RandomPool {

    //对象key的index位置
    private HashMap<String, Integer> keyMap;
    //index位置记录的对象
    private HashMap<Integer, String> indexMap;
    //容量大小
    private int size;

    private void insert(String key) {
        if (!keyMap.containsKey(key)) {
            keyMap.put(key, size);
            indexMap.put(size++, key);
        }
    }

    /**
     * 删除是为了保持时间复杂度都是0(1)，需要用最后一个元素覆盖删除位置的元素，才能保证getRandom的时间复杂度都是0(1)
     * @param key
     */
    private void delete(String key) {
        if (keyMap.containsKey(key)) {
            Integer deleteIndex = keyMap.get(key);
            //用最后一个元素覆盖删除位置的元素
            String lastkey = indexMap.get(size-1);
            indexMap.put(deleteIndex, lastkey);
            keyMap.put(lastkey, deleteIndex);
            //删除最后一个元素
            keyMap.remove(lastkey);
            indexMap.remove(size-1);
            size--;
        }
    }

    private String getRandom() {
        if (size == 0) return null;
        //随机index
        int random = (int) (Math.random()*size);
        return indexMap.get(random);
    }
}
